home *** CD-ROM | disk | FTP | other *** search
/ InterCD 2000 September / september_2000.iso / intercd / root / ^Linux / cdrtools-1.10 / libhfs_iso / btree.c < prev    next >
Encoding:
C/C++ Source or Header  |  2000-03-05  |  14.7 KB  |  742 lines
  1. /*
  2.  * hfsutils - tools for reading and writing Macintosh HFS volumes
  3.  * Copyright (C) 1996, 1997 Robert Leslie
  4.  *
  5.  * This program is free software; you can redistribute it and/or modify
  6.  * it under the terms of the GNU General Public License as published by
  7.  * the Free Software Foundation; either version 2 of the License, or
  8.  * (at your option) any later version.
  9.  *
  10.  * This program is distributed in the hope that it will be useful,
  11.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.  * GNU General Public License for more details.
  14.  *
  15.  * You should have received a copy of the GNU General Public License
  16.  * along with this program; if not, write to the Free Software
  17.  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  */
  19.  
  20. #include <mconfig.h>
  21. #include <stdxlib.h>
  22. #include <strdefs.h>
  23. #include <errno.h>
  24.  
  25. #include "internal.h"
  26. #include "data.h"
  27. #include "block.h"
  28. #include "file.h"
  29. #include "btree.h"
  30. #include "node.h"
  31.  
  32. /*
  33.  * NAME:    btree->getnode()
  34.  * DESCRIPTION:    retrieve a numbered node from a B*-tree file
  35.  */
  36. int bt_getnode(np)
  37.     node    *np;
  38. {
  39.   btree *bt = np->bt;
  40.   block *bp = &np->data;
  41.   unsigned char *ptr;
  42.   int i;
  43.  
  44.   /* verify the node exists and is marked as in-use */
  45.  
  46.   if (np->nnum < 0 || (np->nnum > 0 && np->nnum >= bt->hdr.bthNNodes))
  47.     {
  48.       ERROR(EIO, "read nonexistent b*-tree node");
  49.       return -1;
  50.     }
  51.  
  52.   if (bt->map && ! BMTST(bt->map, np->nnum))
  53.     {
  54.       ERROR(EIO, "read unallocated b*-tree node");
  55.       return -1;
  56.     }
  57.  
  58.   if (f_getblock(&bt->f, np->nnum, bp) < 0)
  59.     return -1;
  60.  
  61.   ptr = *bp;
  62.  
  63.   d_fetchl(&ptr, (long *) &np->nd.ndFLink);
  64.   d_fetchl(&ptr, (long *) &np->nd.ndBLink);
  65.   d_fetchb(&ptr, (char *) &np->nd.ndType);
  66.   d_fetchb(&ptr, (char *) &np->nd.ndNHeight);
  67.   d_fetchw(&ptr, (short *) &np->nd.ndNRecs);
  68.   d_fetchw(&ptr, &np->nd.ndResv2);
  69.  
  70.   if (np->nd.ndNRecs > HFS_MAXRECS)
  71.     {
  72.       ERROR(EIO, "too many b*-tree node records");
  73.       return -1;
  74.     }
  75.  
  76.   i = np->nd.ndNRecs + 1;
  77.  
  78.   ptr = *bp + HFS_BLOCKSZ - (2 * i);
  79.  
  80.   while (i--)
  81.     d_fetchw(&ptr, (short *) &np->roff[i]);
  82.  
  83.   return 0;
  84. }
  85.  
  86. /*
  87.  * NAME:    btree->putnode()
  88.  * DESCRIPTION:    store a numbered node into a B*-tree file
  89.  */
  90. int bt_putnode(np)
  91.     node    *np;
  92. {
  93.   btree *bt = np->bt;
  94.   block *bp = &np->data;
  95.   unsigned char *ptr;
  96.   int i;
  97.  
  98.   /* verify the node exists and is marked as in-use */
  99.  
  100.   if (np->nnum && np->nnum >= bt->hdr.bthNNodes)
  101.     {
  102.       ERROR(EIO, "write nonexistent b*-tree node");
  103.       return -1;
  104.     }
  105.   else if (bt->map && ! BMTST(bt->map, np->nnum))
  106.     {
  107.       ERROR(EIO, "write unallocated b*-tree node");
  108.       return -1;
  109.     }
  110.  
  111.   ptr = *bp;
  112.  
  113.   d_storel(&ptr, np->nd.ndFLink);
  114.   d_storel(&ptr, np->nd.ndBLink);
  115.   d_storeb(&ptr, np->nd.ndType);
  116.   d_storeb(&ptr, np->nd.ndNHeight);
  117.   d_storew(&ptr, np->nd.ndNRecs);
  118.   d_storew(&ptr, np->nd.ndResv2);
  119.  
  120.   if (np->nd.ndNRecs > HFS_MAXRECS)
  121.     {
  122.       ERROR(EIO, "too many b*-tree node records");
  123.       return -1;
  124.     }
  125.  
  126.   i = np->nd.ndNRecs + 1;
  127.  
  128.   ptr = *bp + HFS_BLOCKSZ - (2 * i);
  129.  
  130.   while (i--)
  131.     d_storew(&ptr, np->roff[i]);
  132.  
  133.   if (f_putblock(&bt->f, np->nnum, bp) < 0)
  134.     return -1;
  135.  
  136.   return 0;
  137. }
  138.  
  139. /*
  140.  * NAME:    btree->readhdr()
  141.  * DESCRIPTION:    read the header node of a B*-tree
  142.  */
  143. int bt_readhdr(bt)
  144.     btree    *bt;
  145. {
  146.   unsigned char *ptr;
  147.   char *map;
  148.   int i;
  149.   unsigned long nnum;
  150.  
  151.   bt->hdrnd.bt   = bt;
  152.   bt->hdrnd.nnum = 0;
  153.  
  154.   if (bt_getnode(&bt->hdrnd) < 0)
  155.     return -1;
  156.  
  157.   if (bt->hdrnd.nd.ndType != ndHdrNode ||
  158.       bt->hdrnd.nd.ndNRecs != 3 ||
  159.       bt->hdrnd.roff[0] != 0x00e ||
  160.       bt->hdrnd.roff[1] != 0x078 ||
  161.       bt->hdrnd.roff[2] != 0x0f8 ||
  162.       bt->hdrnd.roff[3] != 0x1f8)
  163.     {
  164.       ERROR(EIO, "malformed b*-tree header node");
  165.       return -1;
  166.     }
  167.  
  168.   /* read header record */
  169.  
  170.   ptr = HFS_NODEREC(bt->hdrnd, 0);
  171.  
  172.   d_fetchw(&ptr, (short *) &bt->hdr.bthDepth);
  173.   d_fetchl(&ptr, (long *) &bt->hdr.bthRoot);
  174.   d_fetchl(&ptr, (long *) &bt->hdr.bthNRecs);
  175.   d_fetchl(&ptr, (long *) &bt->hdr.bthFNode);
  176.   d_fetchl(&ptr, (long *) &bt->hdr.bthLNode);
  177.   d_fetchw(&ptr, (short *) &bt->hdr.bthNodeSize);
  178.   d_fetchw(&ptr, (short *) &bt->hdr.bthKeyLen);
  179.   d_fetchl(&ptr, (long *) &bt->hdr.bthNNodes);
  180.   d_fetchl(&ptr, (long *) &bt->hdr.bthFree);
  181.  
  182.   for (i = 0; i < 76; ++i)
  183.     d_fetchb(&ptr, (char *) &bt->hdr.bthResv[i]);
  184.  
  185.   if (bt->hdr.bthNodeSize != HFS_BLOCKSZ)
  186.     {
  187.       ERROR(EINVAL, "unsupported b*-tree node size");
  188.       return -1;
  189.     }
  190.  
  191.   /* read map record; construct btree bitmap */
  192.   /* don't set bt->map until we're done, since getnode() checks it */
  193.  
  194.   map = ALLOC(char, HFS_MAP1SZ);
  195.   if (map == 0)
  196.     {
  197.       ERROR(ENOMEM, 0);
  198.       return -1;
  199.     }
  200.  
  201.   memcpy(map, HFS_NODEREC(bt->hdrnd, 2), HFS_MAP1SZ);
  202.   bt->mapsz = HFS_MAP1SZ;
  203.  
  204.   /* read continuation map records, if any */
  205.  
  206.   nnum = bt->hdrnd.nd.ndFLink;
  207.  
  208.   while (nnum)
  209.     {
  210.       node n;
  211.       char *newmap;
  212.  
  213.       n.bt   = bt;
  214.       n.nnum = nnum;
  215.  
  216.       if (bt_getnode(&n) < 0)
  217.     {
  218.       FREE(map);
  219.       return -1;
  220.     }
  221.  
  222.       if (n.nd.ndType != ndMapNode ||
  223.       n.nd.ndNRecs != 1 ||
  224.       n.roff[0] != 0x00e ||
  225.       n.roff[1] != 0x1fa)
  226.     {
  227.       FREE(map);
  228.       ERROR(EIO, "malformed b*-tree map node");
  229.       return -1;
  230.     }
  231.  
  232.       newmap = REALLOC(map, char, bt->mapsz + HFS_MAPXSZ);
  233.       if (newmap == 0)
  234.     {
  235.       FREE(map);
  236.       ERROR(ENOMEM, 0);
  237.       return -1;
  238.     }
  239.       map = newmap;
  240.  
  241.       memcpy(map + bt->mapsz, HFS_NODEREC(n, 0), HFS_MAPXSZ);
  242.       bt->mapsz += HFS_MAPXSZ;
  243.  
  244.       nnum = n.nd.ndFLink;
  245.     }
  246.  
  247.   bt->map = map;
  248.  
  249.   return 0;
  250. }
  251.  
  252. /*
  253.  * NAME:    btree->writehdr()
  254.  * DESCRIPTION:    write the header node of a B*-tree
  255.  */
  256. int bt_writehdr(bt)
  257.     btree    *bt;
  258. {
  259.   unsigned char *ptr;
  260.   char *map;
  261.   unsigned long mapsz, nnum;
  262.   int i;
  263.  
  264.   if (bt->hdrnd.bt != bt ||
  265.       bt->hdrnd.nnum != 0 ||
  266.       bt->hdrnd.nd.ndType != ndHdrNode ||
  267.       bt->hdrnd.nd.ndNRecs != 3)
  268.     abort();
  269.  
  270.   ptr = HFS_NODEREC(bt->hdrnd, 0);
  271.  
  272.   d_storew(&ptr, bt->hdr.bthDepth);
  273.   d_storel(&ptr, bt->hdr.bthRoot);
  274.   d_storel(&ptr, bt->hdr.bthNRecs);
  275.   d_storel(&ptr, bt->hdr.bthFNode);
  276.   d_storel(&ptr, bt->hdr.bthLNode);
  277.   d_storew(&ptr, bt->hdr.bthNodeSize);
  278.   d_storew(&ptr, bt->hdr.bthKeyLen);
  279.   d_storel(&ptr, bt->hdr.bthNNodes);
  280.   d_storel(&ptr, bt->hdr.bthFree);
  281.  
  282.   for (i = 0; i < 76; ++i)
  283.     d_storeb(&ptr, bt->hdr.bthResv[i]);
  284.  
  285.   memcpy(HFS_NODEREC(bt->hdrnd, 2), bt->map, HFS_MAP1SZ);
  286.  
  287.   if (bt_putnode(&bt->hdrnd) < 0)
  288.     return -1;
  289.  
  290.   map   = bt->map   + HFS_MAP1SZ;
  291.   mapsz = bt->mapsz - HFS_MAP1SZ;
  292.  
  293.   nnum  = bt->hdrnd.nd.ndFLink;
  294.  
  295.   while (mapsz)
  296.     {
  297.       node n;
  298.  
  299.       if (nnum == 0)
  300.     {
  301.       ERROR(EIO, "truncated b*-tree map");
  302.       return -1;
  303.     }
  304.  
  305.       n.bt   = bt;
  306.       n.nnum = nnum;
  307.  
  308.       if (bt_getnode(&n) < 0)
  309.     return -1;
  310.  
  311.       if (n.nd.ndType != ndMapNode ||
  312.       n.nd.ndNRecs != 1 ||
  313.       n.roff[0] != 0x00e ||
  314.       n.roff[1] != 0x1fa)
  315.     {
  316.       ERROR(EIO, "malformed b*-tree map node");
  317.       return -1;
  318.     }
  319.  
  320.       memcpy(HFS_NODEREC(n, 0), map, HFS_MAPXSZ);
  321.  
  322.       if (bt_putnode(&n) < 0)
  323.     return -1;
  324.  
  325.       map   += HFS_MAPXSZ;
  326.       mapsz -= HFS_MAPXSZ;
  327.  
  328.       nnum = n.nd.ndFLink;
  329.     }
  330.  
  331.   bt->flags &= ~HFS_UPDATE_BTHDR;
  332.  
  333.   return 0;
  334. }
  335.  
  336. /* High-Level B*-Tree Routines ============================================= */
  337.  
  338. /*
  339.  * NAME:    btree->space()
  340.  * DESCRIPTION:    assert space for new records, or extend the file
  341.  */
  342. int bt_space(bt, nrecs)
  343.     btree        *bt;
  344.     unsigned int    nrecs;
  345. {
  346.   unsigned int nnodes;
  347.   int space;
  348.  
  349.   nnodes = nrecs * (bt->hdr.bthDepth + 1);
  350.  
  351.   if (nnodes <= bt->hdr.bthFree)
  352.     return 0;
  353.  
  354.   /* make sure the extents tree has room too */
  355.  
  356.   if (bt != &bt->f.vol->ext)
  357.     {
  358.       if (bt_space(&bt->f.vol->ext, 1) < 0)
  359.     return -1;
  360.     }
  361.  
  362.   space = f_alloc(&bt->f);
  363.   if (space < 0)
  364.     return -1;
  365.  
  366.   nnodes = space * (bt->f.vol->mdb.drAlBlkSiz / bt->hdr.bthNodeSize);
  367.  
  368.   bt->hdr.bthNNodes += nnodes;
  369.   bt->hdr.bthFree   += nnodes;
  370.  
  371.   bt->flags |= HFS_UPDATE_BTHDR;
  372.  
  373.   bt->f.vol->flags |= HFS_UPDATE_ALTMDB;
  374.  
  375.   while (bt->hdr.bthNNodes > bt->mapsz * 8)
  376.     {
  377.       char *newmap;
  378.       node mapnd;
  379.  
  380.       /* extend tree map */
  381.  
  382.       newmap = REALLOC(bt->map, char, bt->mapsz + HFS_MAPXSZ);
  383.       if (newmap == 0)
  384.     {
  385.       ERROR(ENOMEM, 0);
  386.       return -1;
  387.     }
  388.  
  389.       memset(newmap + bt->mapsz, 0, HFS_MAPXSZ);
  390.  
  391.       bt->map    = newmap;
  392.       bt->mapsz += HFS_MAPXSZ;
  393.  
  394.       n_init(&mapnd, bt, ndMapNode, 0);
  395.       if (n_new(&mapnd) < 0)
  396.     return -1;
  397.  
  398.       /* link the new map node */
  399.  
  400.       if (bt->hdrnd.nd.ndFLink == 0)
  401.     {
  402.       bt->hdrnd.nd.ndFLink = mapnd.nnum;
  403.       mapnd.nd.ndBLink     = 0;
  404.     }
  405.       else
  406.     {
  407.       node n;
  408.  
  409.       n.bt   = bt;
  410.       n.nnum = bt->hdrnd.nd.ndFLink;
  411.  
  412.       while (1)
  413.         {
  414.           if (bt_getnode(&n) < 0)
  415.         return -1;
  416.  
  417.           if (n.nd.ndFLink == 0)
  418.         break;
  419.  
  420.           n.nnum = n.nd.ndFLink;
  421.         }
  422.  
  423.       n.nd.ndFLink     = mapnd.nnum;
  424.       mapnd.nd.ndBLink = n.nnum;
  425.  
  426.       if (bt_putnode(&n) < 0)
  427.         return -1;
  428.     }
  429.  
  430.       mapnd.nd.ndNRecs = 1;
  431.       mapnd.roff[1]    = 0x1fa;
  432.  
  433.       if (bt_putnode(&mapnd) < 0)
  434.     return -1;
  435.     }
  436.  
  437.   return 0;
  438. }
  439.  
  440. /*
  441.  * NAME:    btree->insertx()
  442.  * DESCRIPTION:    recursively locate a node and insert a record
  443.  */
  444. int bt_insertx(np, record, reclen)
  445.     node        *np;
  446.     unsigned char    *record;
  447.     int        *reclen;
  448. {
  449.   node child;
  450.   unsigned char *rec;
  451.  
  452.   if (n_search(np, record))
  453.     {
  454.       ERROR(EIO, "b*-tree record already exists");
  455.       return -1;
  456.     }
  457.  
  458.   switch ((unsigned char) np->nd.ndType)
  459.     {
  460.     case ndIndxNode:
  461.       if (np->rnum < 0)
  462.     rec = HFS_NODEREC(*np, 0);
  463.       else
  464.     rec = HFS_NODEREC(*np, np->rnum);
  465.  
  466.       child.bt   = np->bt;
  467.       child.nnum = d_getl(HFS_RECDATA(rec));
  468.  
  469.       if (bt_getnode(&child) < 0 ||
  470.       bt_insertx(&child, record, reclen) < 0)
  471.     return -1;
  472.  
  473.       if (np->rnum < 0)
  474.     {
  475.       n_index(np->bt, HFS_NODEREC(child, 0), child.nnum, rec, 0);
  476.       if (*reclen == 0)
  477.         return bt_putnode(np);
  478.     }
  479.  
  480.       return *reclen ? n_insert(np, record, reclen) : 0;
  481.  
  482.     case ndLeafNode:
  483.       return n_insert(np, record, reclen);
  484.  
  485.     default:
  486.       ERROR(EIO, "unexpected b*-tree node");
  487.       return -1;
  488.     }
  489. }
  490.  
  491. /*
  492.  * NAME:    btree->insert()
  493.  * DESCRIPTION:    insert a new node record into a tree
  494.  */
  495. int bt_insert(bt, record, reclen)
  496.     btree        *bt;
  497.     unsigned char    *record;
  498.     int        reclen;
  499. {
  500.   node root;
  501.  
  502.   if (bt->hdr.bthRoot == 0)
  503.     {
  504.       /* create root node */
  505.  
  506.       n_init(&root, bt, ndLeafNode, 1);
  507.       if (n_new(&root) < 0 ||
  508.       bt_putnode(&root) < 0)
  509.     return -1;
  510.  
  511.       bt->hdr.bthDepth = 1;
  512.       bt->hdr.bthRoot  = root.nnum;
  513.       bt->hdr.bthFNode = root.nnum;
  514.       bt->hdr.bthLNode = root.nnum;
  515.  
  516.       bt->flags |= HFS_UPDATE_BTHDR;
  517.     }
  518.   else
  519.     {
  520.       root.bt   = bt;
  521.       root.nnum = bt->hdr.bthRoot;
  522.  
  523.       if (bt_getnode(&root) < 0)
  524.     return -1;
  525.     }
  526.  
  527.   if (bt_insertx(&root, record, &reclen) < 0)
  528.     return -1;
  529.  
  530.   if (reclen)
  531.     {
  532.       unsigned char oroot[HFS_MAXRECLEN];
  533.       int orootlen;
  534.  
  535.       /* root node was split; create a new root */
  536.  
  537.       n_index(bt, HFS_NODEREC(root, 0), root.nnum, oroot, &orootlen);
  538.  
  539.       n_init(&root, bt, ndIndxNode, root.nd.ndNHeight + 1);
  540.       if (n_new(&root) < 0)
  541.     return -1;
  542.  
  543.       ++bt->hdr.bthDepth;
  544.       bt->hdr.bthRoot = root.nnum;
  545.  
  546.       bt->flags |= HFS_UPDATE_BTHDR;
  547.  
  548.       /* insert index records for new root */
  549.  
  550.       n_search(&root, oroot);
  551.       n_insertx(&root, oroot, orootlen);
  552.  
  553.       n_search(&root, record);
  554.       n_insertx(&root, record, reclen);
  555.  
  556.       if (bt_putnode(&root) < 0)
  557.     return -1;
  558.     }
  559.  
  560.   ++bt->hdr.bthNRecs;
  561.   bt->flags |= HFS_UPDATE_BTHDR;
  562.  
  563.   return 0;
  564. }
  565.  
  566. /*
  567.  * NAME:    btree->deletex()
  568.  * DESCRIPTION:    recursively locate a node and delete a record
  569.  */
  570. int bt_deletex(np, key, record, flag)
  571.     node        *np;
  572.     unsigned char    *key;
  573.     unsigned char    *record;
  574.     int        *flag;
  575. {
  576.   node child;
  577.   unsigned char *rec;
  578.   int found;
  579.  
  580.   found = n_search(np, key);
  581.  
  582.   switch ((unsigned char) np->nd.ndType)
  583.     {
  584.     case ndIndxNode:
  585.       if (np->rnum < 0)
  586.     {
  587.       ERROR(EIO, "b*-tree record not found");
  588.       return -1;
  589.     }
  590.  
  591.       rec = HFS_NODEREC(*np, np->rnum);
  592.  
  593.       child.bt   = np->bt;
  594.       child.nnum = d_getl(HFS_RECDATA(rec));
  595.  
  596.       if (bt_getnode(&child) < 0 ||
  597.       bt_deletex(&child, key, rec, flag) < 0)
  598.     return -1;
  599.  
  600.       if (*flag)
  601.     {
  602.       *flag = 0;
  603.  
  604.       if (HFS_RECKEYLEN(rec) == 0)
  605.         return n_delete(np, record, flag);
  606.  
  607.       if (np->rnum == 0)
  608.         {
  609.           n_index(np->bt, HFS_NODEREC(*np, 0), np->nnum, record, 0);
  610.           *flag = 1;
  611.         }
  612.  
  613.       return bt_putnode(np);
  614.     }
  615.  
  616.       return 0;
  617.  
  618.     case ndLeafNode:
  619.       if (found == 0)
  620.     {
  621.       ERROR(EIO, "b*-tree record not found");
  622.       return -1;
  623.     }
  624.  
  625.       return n_delete(np, record, flag);
  626.  
  627.     default:
  628.       ERROR(EIO, "unexpected b*-tree node");
  629.       return -1;
  630.     }
  631. }
  632.  
  633. /*
  634.  * NAME:    btree->delete()
  635.  * DESCRIPTION:    remove a node record from a tree
  636.  */
  637. int bt_delete(bt, key)
  638.     btree        *bt;
  639.     unsigned char    *key;
  640. {
  641.   node root;
  642.   unsigned char record[HFS_MAXRECLEN];
  643.   int flag = 0;
  644.  
  645.   root.bt   = bt;
  646.   root.nnum = bt->hdr.bthRoot;
  647.  
  648.   if (root.nnum == 0)
  649.     {
  650.       ERROR(EIO, "empty b*-tree");
  651.       return -1;
  652.     }
  653.  
  654.   if (bt_getnode(&root) < 0 ||
  655.       bt_deletex(&root, key, record, &flag) < 0)
  656.     return -1;
  657.  
  658.   if (bt->hdr.bthDepth > 1 && root.nd.ndNRecs == 1)
  659.     {
  660.       unsigned char *rec;
  661.  
  662.       /* chop the root */
  663.  
  664.       rec = HFS_NODEREC(root, 0);
  665.  
  666.       --bt->hdr.bthDepth;
  667.       bt->hdr.bthRoot = d_getl(HFS_RECDATA(rec));
  668.  
  669.       n_free(&root);
  670.     }
  671.   else if (bt->hdr.bthDepth == 1 && root.nd.ndNRecs == 0)
  672.     {
  673.       /* delete the root node */
  674.  
  675.       bt->hdr.bthDepth = 0;
  676.       bt->hdr.bthRoot  = 0;
  677.       bt->hdr.bthFNode = 0;
  678.       bt->hdr.bthLNode = 0;
  679.  
  680.       n_free(&root);
  681.     }
  682.  
  683.   --bt->hdr.bthNRecs;
  684.   bt->flags |= HFS_UPDATE_BTHDR;
  685.  
  686.   return 0;
  687. }
  688.  
  689. /*
  690.  * NAME:    btree->search()
  691.  * DESCRIPTION:    locate a data record given a search key
  692.  */
  693. int bt_search(bt, key, np)
  694.     btree        *bt;
  695.     unsigned char    *key;
  696.     node        *np;
  697. {
  698.   np->bt   = bt;
  699.   np->nnum = bt->hdr.bthRoot;
  700.  
  701.   if (np->nnum == 0)
  702.     {
  703.       ERROR(ENOENT, 0);
  704.       return 0;
  705.     }
  706.  
  707.   while (1)
  708.     {
  709.       int found;
  710.       unsigned char *rec;
  711.  
  712.       if (bt_getnode(np) < 0)
  713.     return -1;
  714.  
  715.       found = n_search(np, key);
  716.  
  717.       switch ((unsigned char) np->nd.ndType)
  718.     {
  719.     case ndIndxNode:
  720.       if (np->rnum < 0)
  721.         {
  722.           ERROR(ENOENT, 0);
  723.           return 0;
  724.         }
  725.  
  726.       rec = HFS_NODEREC(*np, np->rnum);
  727.       np->nnum = d_getl(HFS_RECDATA(rec));
  728.       break;
  729.  
  730.     case ndLeafNode:
  731.       if (! found)
  732.         ERROR(ENOENT, 0);
  733.  
  734.       return found;
  735.  
  736.     default:
  737.       ERROR(EIO, "unexpected b*-tree node");
  738.       return -1;
  739.     }
  740.     }
  741. }
  742.